-- p. 70 #10--13

import List (delete, sortBy)

-- This type is the solution to exercise 10, but we don't use it; see
-- turnDirection.
data Direction = DirLeft | DirStraight | DirRight
                 deriving (Show)

type Point = (Integer, Integer)

-- 'subtractPoint p1 p2' is the vector from p2 to p1.
subtractPoint :: Point -> Point -> Point
subtractPoint (x1,y1) (x2,y2) = (x1-x2, y1-y2)

--- 'crossProductLength p1 p2' is the length of the vector that is the
--- cross product of p1 and p2.
crossProductLength :: Point -> Point -> Integer
crossProductLength (x1,y1) (x2,y2) = x1*y2 - x2*y1

-- p. 70 ex 11
--
-- It's more convenient to return the Prelude's Ordering type than
-- Direction, since that's what 'sortBy' expects. 'LT' indicates a
-- left turn, 'GT' a right turn, and 'EQ' a straight line.
-- 
-- Counter-clockwise rotation is usually considered 'positive', so
-- it's a bit odd to return 'LT' for left turns, but we want
-- (turnDirection pivot) to be a comparison function on points that
-- directs sortBy to put them in counter-clockwise order.
turnDirection :: Point -> Point -> Point -> Ordering
turnDirection p1 p2 p3 =
    -- Make everything relative to p1.
    let p2' = subtractPoint p2 p1
        p3' = subtractPoint p3 p1
    in compare 0 (crossProductLength p2' p3')

--- p. 70 ex 12
--- Given a list of three or more points, return a list of the
--- directions of the turns taken in following the path the points
--- take.
turnDirections :: [Point] -> [Ordering]
turnDirections (p1: ps @ (p2:p3:rest))
    = turnDirection p1 p2 p3 : turnDirections ps
turnDirections _ = []

-- 'leftBottomPoint ps' is the leftmost point in ps; if there is more
-- than one such point, it is the lowest among them.
leftBottomPoint :: [Point] -> Point
-- Conveniently, Haskell defines < on tuples, and thus min is defined
-- as well, with the meaning we need.
leftBottomPoint (p:ps) = foldr min p ps

-- p. 70 ex 13
scan (p2:p1:cwtail) (p3:ccwtail) =
    if turnDirection p1 p2 p3 == GT
    then scan (p1:cwtail) (p3:ccwtail)
    else scan (p3:p2:p1:cwtail) ccwtail
scan cw [] = cw

-- convexHull ps is a sequence of points forming a convex hull around ps.
convexHull :: [Point] -> [Point]
convexHull ps @ (_:_:_) =
    let pivot = leftBottomPoint ps
        (first:rest) = sortBy (turnDirection pivot) (delete pivot ps)
    in scan [first,pivot] rest

-- Notes, after reading David's solution:
--
-- Neither of us wrote the solution to ex 13 using the solution to ex 12.
--
-- My leftBottomPoint is Prelude 'minimum'.
--
-- removeRightTurns is a better name than 'scan'.
--
-- Whereas I treat the pivot as being outside the rest of the dataset,
-- David's code treats grahamScanSort as returning a non-convex hull
-- (i.e., the pivot is just another point), and then makes it convex.
